package 字符串;

/**
 * 外观数组  38
 * 给定一个正整数 n，输出外观数列的第 n 项。
 *
 * “外观数列”是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列：
 *
 * countAndSay(1) = "1"
 * countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
 * 前五项如下：
 * "1"
 * "11"
 * "21"
 * "1211"
 * "111221"
 *
 * 解题思路：  因为当前项是对前一项值的描述，所以自然而然想到递归， 先递归实现，然后优化为迭代
   解题步骤：
    1：递归终止条件， 因为是对前一项的描述，所以 n = 1时 为1，返回当前值
    2: 分析前一项： 前一项转换为数组，遍历，定义一个计数器，如果当前索引与前一个值相等，则count++，返回，直到不相等，count+当前值做拼接
                  如果不相等，则直接拼接，遍历下一个元素，直到遍历返回
    3： 返回当前值，进行回溯
 *
 * @Author lf
 * @Date 3/29/2024
 */
public class CountAndSay {
    public String countAndSay(int n) {
        if(n == 1){
            return "1";
        }
        String pre = countAndSay(n - 1);
        // 进行递归逻辑
        StringBuilder res = new StringBuilder();
        int count =1;
        for (int i = 0; i < pre.length(); i++) {
           // 如果当前元素与下一个元素相等，则遍历下一个元素,直到不相等
            if(i< pre.length() -1 && pre.charAt(i) == pre.charAt(i+1)){
               count++;
               continue;
           }
           // 拼接count与当前值
           res.append(count).append(pre.charAt(i));
            // 拼接完后count恢复默认
            count = 1;
        }
        return res.toString();
    }

    /**
     * 使用迭代实现
     * 为啥可以使用迭代实现，因为n是连续的，所以可以考虑迭代实现，下一个值是上一个值的描述，所以循环即可
     * 递归可以直接改为循环，内部逻辑是不变的，外部每次循环完，内部计算出pre值即可。
     * @param n
     * @return
     */
    public String countAndSayByIterable(int n){
        if(n == 1){
            return "1";
        }
        String pre = "1";
        // n倒着减，到0也是n次
        while (--n>0){
            StringBuilder res = new StringBuilder();
            int count =1;
            for (int i = 0; i < pre.length(); i++) {
                // 如果当前元素与下一个元素相等，则遍历下一个元素,直到不相等
                if(i< pre.length() -1 && pre.charAt(i) == pre.charAt(i+1)){
                    count++;
                    continue;
                }
                // 拼接count与当前值
                res.append(count).append(pre.charAt(i));
                // 拼接完后count恢复默认
                count = 1;
            }
            pre = res.toString();
        }
        return pre;
    }

    public static void main(String[] args) {
        CountAndSay countAndSay = new CountAndSay();

        System.out.println(countAndSay.countAndSay(10));

        System.out.println(countAndSay.countAndSayByIterable(10));

    }
}
